{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Difference Between Maximum and Minimum Price Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxOutput"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大价值和与最小价值和的差值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code>&nbsp;个节点的无向无根图，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。给你一个整数&nbsp;<code>n</code>&nbsp;和一个长度为 <code>n - 1</code>&nbsp;的二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示树中节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条边。</p>\n",
    "\n",
    "<p>每个节点都有一个价值。给你一个整数数组&nbsp;<code>price</code>&nbsp;，其中&nbsp;<code>price[i]</code>&nbsp;是第 <code>i</code>&nbsp;个节点的价值。</p>\n",
    "\n",
    "<p>一条路径的 <strong>价值和</strong>&nbsp;是这条路径上所有节点的价值之和。</p>\n",
    "\n",
    "<p>你可以选择树中任意一个节点作为根节点&nbsp;<code>root</code>&nbsp;。选择 <code>root</code>&nbsp;为根的 <strong>开销</strong>&nbsp;是以 <code>root</code>&nbsp;为起点的所有路径中，<strong>价值和</strong>&nbsp;最大的一条路径与最小的一条路径的差值。</p>\n",
    "\n",
    "<p>请你返回所有节点作为根节点的选择中，<strong>最大</strong>&nbsp;的 <strong>开销</strong>&nbsp;为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/01/example14.png\" style=\"width: 556px; height: 231px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]\n",
    "<b>输出：</b>24\n",
    "<b>解释：</b>上图展示了以节点 2 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。\n",
    "- 第一条路径节点为 [2,1,3,4]：价值为 [7,8,6,10] ，价值和为 31 。\n",
    "- 第二条路径节点为 [2] ，价值为 [7] 。\n",
    "最大路径和与最小路径和的差值为 24 。24 是所有方案中的最大开销。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/24/p1_example2.png\" style=\"width: 352px; height: 184px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, edges = [[0,1],[1,2]], price = [1,1,1]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>上图展示了以节点 0 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。\n",
    "- 第一条路径包含节点 [0,1,2]：价值为 [1,1,1] ，价值和为 3 。\n",
    "- 第二条路径节点为 [0] ，价值为 [1] 。\n",
    "最大路径和与最小路径和的差值为 2 。2 是所有方案中的最大开销。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>edges</code> 表示一棵符合题面要求的树。</li>\n",
    "\t<li><code>price.length == n</code></li>\n",
    "\t<li><code>1 &lt;= price[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [difference-between-maximum-and-minimum-price-sum](https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [difference-between-maximum-and-minimum-price-sum](https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[0,1],[1,2],[1,3],[3,4],[3,5]]\\n[9,8,7,6,10,5]', '3\\n[[0,1],[1,2]]\\n[1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            g[e[0]].append(e[1])\n",
    "            g[e[1]].append(e[0])\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i: int, fa: int) -> (int, int):\n",
    "            max_s1 = price[i]\n",
    "            max_s2 = 0\n",
    "\n",
    "            for j in g[i]:\n",
    "                if j == fa:\n",
    "                    continue\n",
    "                s1, s2 = dfs(j, i)\n",
    "\n",
    "                nonlocal ans\n",
    "                ans = max(ans, max_s1 + s2, max_s2 + s1)\n",
    "\n",
    "                max_s1 = max(max_s1, s1 + price[i])\n",
    "                max_s2 = max(max_s2, s2 + price[i])\n",
    "\n",
    "            return max_s1, max_s2\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            nonlocal ans\n",
    "            max_s1 = p = price[x]\n",
    "            max_s2 = 0\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                s1, s2 = dfs(y, x)\n",
    "\n",
    "                ans = max(ans, max_s1 + s2, max_s2 + s1)\n",
    "                max_s1 = max(max_s1, s1 + p)\n",
    "                max_s2 = max(max_s2, s2 + p)\n",
    "\n",
    "            return max_s1, max_s2\n",
    "        \n",
    "        dfs(0, -1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            nonlocal ans\n",
    "            max_s1 = p = price[x]\n",
    "            max_s2 = 0\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                s1, s2 = dfs(y, x)\n",
    "                # 前面最大带叶子的路径和 + 当前不带叶子的路径和\n",
    "                # 前面最大不带叶子的路径和 + 当前带叶子的路径和\n",
    "                ans = max(ans, max_s1 + s2, max_s2 + s1)\n",
    "                max_s1 = max(max_s1, s1 + p)\n",
    "                max_s2 = max(max_s2, s2 + p)  # 这里加上 p 是因为 x 必然不是叶子\n",
    "            return max_s1, max_s2\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/solutions/2062782/by-endlesscheng-5l70/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        # 由于所有节点对应的价值都是正数，那么最大价值和的路径必然越长越好，也就是说会延伸到叶子\n",
    "        # 最小价值和路径必然只包含一个节点，那么最大开销就是不带叶子的路径和\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(x, fa):\n",
    "            nonlocal ans\n",
    "            max_s1, max_s2 = price[x], 0\n",
    "            for y in g[x]:\n",
    "                if y==fa: # 不走回头路\n",
    "                    continue\n",
    "                s1, s2 = dfs(y, x)\n",
    "                ans = max(max_s1+s2, max_s2+s1, ans)\n",
    "                max_s1=max(s1+price[x], max_s1)\n",
    "                max_s2=max(max_s2, s2+price[x])\n",
    "            return max_s1, max_s2\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        neighbours = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            neighbours[u].append(v)\n",
    "            neighbours[v].append(u)\n",
    "        parent = [-1] * n\n",
    "        parent[0] = 0\n",
    "        a = [0]\n",
    "        i = 0\n",
    "        while i < len(a):\n",
    "            u = a[i]\n",
    "            i += 1\n",
    "            for v in neighbours[u]:\n",
    "                if parent[v] == -1:\n",
    "                    parent[v] = u\n",
    "                    a.append(v)\n",
    "        res = 0\n",
    "        score = [None] * n\n",
    "        for i in reversed(range(1, n)):\n",
    "            v = a[i]\n",
    "            u = parent[v]\n",
    "            if score[v]:\n",
    "                if score[u]:\n",
    "                    res = max(res, score[u][0] + score[v][1])\n",
    "                    res = max(res, score[u][1] + score[v][0])\n",
    "                    score[u][0] = max(score[u][0], price[u] + score[v][0])\n",
    "                    score[u][1] = max(score[u][1], price[u] + score[v][1])\n",
    "                else:\n",
    "                    res = max(res, price[u] + score[v][0])\n",
    "                    res = max(res, score[v][1])\n",
    "                    score[u] = [price[u] + score[v][0], price[u] + score[v][1]]\n",
    "                score[v] = None\n",
    "            else:\n",
    "                if score[u]:\n",
    "                    res = max(res, score[u][1])\n",
    "                    res = max(res, score[u][0] + price[v])\n",
    "                    score[u][1] = max(score[u][1], price[u] + price[v])\n",
    "                else:\n",
    "                    res = max(res, price[u])\n",
    "                    res = max(res, price[v])\n",
    "                    score[u] = [price[u], price[u] + price[v]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            tree[u].append(v)\n",
    "            tree[v].append(u)\n",
    "        \n",
    "        mxd = [0] * n\n",
    "        mxchild = [0] * n\n",
    "        sec = [0] * n\n",
    "        def dfs1(x, p) -> int:\n",
    "            for u in tree[x]:\n",
    "                if u == p: continue\n",
    "                temp = dfs1(u, x)\n",
    "                if temp > mxd[x]:\n",
    "                    mxchild[x] = u\n",
    "                    sec[x] = mxd[x] \n",
    "                    mxd[x] = temp\n",
    "                elif temp > sec[x]:\n",
    "                    sec[x] = temp\n",
    "            return mxd[x] + price[x]\n",
    "        dfs1(0, -1)\n",
    "\n",
    "        # print(mxd)\n",
    "        # print(sec)\n",
    "\n",
    "        ans = 0\n",
    "        def dfs2(x, p, s) -> int:\n",
    "            nonlocal ans\n",
    "            ans = max(ans, s, mxd[x])\n",
    "            for u in tree[x]:\n",
    "                if u == p: continue\n",
    "                if u != mxchild[x]:\n",
    "                    ns = price[x] + max(s, mxd[x])\n",
    "                else:\n",
    "                    ns = price[x] + max(s, sec[x])\n",
    "                dfs2(u, x, ns)\n",
    "\n",
    "        dfs2(0, -1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def bfs(x: int):\n",
    "            ans = last = 0\n",
    "            dis = [0] * n\n",
    "            vis = [False] * n\n",
    "            dis[x] = price[x]\n",
    "            vis[x] = True\n",
    "            q = deque([x])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                if dis[x] > dis[last]:\n",
    "                    last = x \n",
    "                for y in g[x]:\n",
    "                    if vis[y]: continue\n",
    "                    q.append(y)\n",
    "                    vis[y] = True\n",
    "                    dis[y] = dis[x] + price[y]\n",
    "                    if dis[x] > ans:\n",
    "                        ans = dis[x]\n",
    "            return last, ans\n",
    "\n",
    "        s, _ = bfs(0)\n",
    "        t, ans1 = bfs(s)\n",
    "        _, ans2 = bfs(t)\n",
    "        return ans1 if ans1 > ans2 else ans2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "        ans = [0]*n\n",
    "        def dfs(x,fa):\n",
    "            x_max = price[x]\n",
    "            x_min = price[x]\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                max_ = dfs(y,x)+price[x]\n",
    "                x_max = max(x_max,max_)\n",
    "            ans[x] = x_max\n",
    "            return x_max\n",
    "        res = 0\n",
    "        def dfs2(x,fa):\n",
    "            nonlocal res\n",
    "            res = max(res,ans[x] - price[x])\n",
    "            m_v = -1\n",
    "            m_id  = -1\n",
    "            sec_v = -1\n",
    "            sec_id = -1\n",
    "            for y in g[x]:\n",
    "                if ans[y] >= m_v:\n",
    "                    sec_id = m_id\n",
    "                    sec_v = m_v\n",
    "                    m_v = ans[y]\n",
    "                    m_id = y\n",
    "                elif ans[y] > sec_v:\n",
    "                    sec_id = y\n",
    "                    sec_v = ans[y]\n",
    "\n",
    "            for y in g[x]:\n",
    "                if y ==  fa:continue\n",
    "                tmp1 = ans[x]\n",
    "                tmp2 = ans[y]\n",
    "                if y == m_id:\n",
    "                    ans[x] = (ans[sec_id] + price[x]) if sec_id!= -1 else price[x]\n",
    "                else:\n",
    "                    ans[x] = ans[m_id] + price[x]\n",
    "                \n",
    "                ans[y] = max(ans[y],ans[x] + price[y])\n",
    "                dfs2(y,x)\n",
    "                ans[x] = tmp1\n",
    "                ans[y] = tmp2     \n",
    "   \n",
    "        dfs(0,-1)\n",
    "       \n",
    "        dfs2(0,-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for a,b in edges :\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x,fa) :\n",
    "            nonlocal ans\n",
    "            # 包含叶子的最大值，不包含叶子的最大值\n",
    "            leaf = p = price[x]\n",
    "            noleaf = 0\n",
    "            for ne in g[x] :\n",
    "                if ne == fa : continue\n",
    "                a,b = dfs(ne,x)\n",
    "\n",
    "                ans = max(ans, a + noleaf, b + leaf)\n",
    "                leaf = max(leaf, a + p)\n",
    "                noleaf = max(noleaf, b + p)\n",
    "            return [leaf,noleaf]\n",
    "        \n",
    "        dfs(0,-1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        if n==1: return 0\n",
    "\n",
    "        al = defaultdict(list)\n",
    "        for v1, v2 in edges:\n",
    "            al[v1].append(v2)\n",
    "            al[v2].append(v1)\n",
    "\n",
    "        ans=0\n",
    "        def dfs(node, fa) -> tuple[int,int]:\n",
    "            if node != 0 and len(al[node])==1:\n",
    "                return (0, price[node])\n",
    "\n",
    "            nonlocal ans\n",
    "            mx0=-price[node]\n",
    "            mx1=0\n",
    "            for c in al[node]:\n",
    "                if c==fa: continue\n",
    "                cx0,cx1 = dfs(c, node)\n",
    "                ans = max(ans, cx0+mx1+price[node], cx1+mx0+price[node])\n",
    "                mx0 = max(mx0, cx0)\n",
    "                mx1 = max(mx1, cx1)\n",
    "            # print(node,mx0+price[node], mx1+price[node])\n",
    "            return mx0+price[node], mx1+price[node]\n",
    "\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        pre = [-1]\n",
    "        res = 0\n",
    "\n",
    "        def dfs(node:int)->tuple:\n",
    "            nonlocal res\n",
    "            if len(graph[node]) == 1 and node != 0:\n",
    "                return price[node],0\n",
    "\n",
    "            sum_val = 0\n",
    "            suffix_val = -price[node]\n",
    "            pre.append(node)\n",
    "            for nex_node in graph[node]:\n",
    "                if nex_node == pre[-2]:\n",
    "                    continue\n",
    "                a, b = dfs(nex_node)\n",
    "                res = max(res, sum_val+price[node]+b,\\\n",
    "                          suffix_val+price[node]+a)\n",
    "                sum_val = max(sum_val,a)\n",
    "                suffix_val = max(suffix_val,b)\n",
    "\n",
    "            pre.pop()\n",
    "            return price[node]+sum_val,price[node]+suffix_val\n",
    "\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        res = 0\n",
    "        def dfs(node, parent):\n",
    "            include, exclude = price[node], 0 \n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                if nei == parent:\n",
    "                    continue \n",
    "                nxt = dfs(nei, node)\n",
    "                res = max(res, nxt[0] + exclude, nxt[1] + include)\n",
    "                include = max(include, nxt[0] + price[node])\n",
    "                exclude = max(exclude, nxt[1] + price[node])\n",
    "            return include, exclude\n",
    "        dfs(0, - 1)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        def dfs1(st,p):\n",
    "            nonlocal maxpr\n",
    "            nonlocal root1\n",
    "            nonlocal used\n",
    "            nonlocal price\n",
    "            for a in arr[st]:\n",
    "                if used[a]==0:\n",
    "                    used[a]=1\n",
    "                    dfs1(a,p+price[a])\n",
    "                    used[a]=0\n",
    "            if p>maxpr:\n",
    "                maxpr=p\n",
    "                root1=st\n",
    "        def dfs2(st,p):\n",
    "            nonlocal dis\n",
    "            nonlocal used\n",
    "            nonlocal price\n",
    "            dis[st]=max(dis[st],p)\n",
    "            for a in arr[st]:\n",
    "                if used[a]==0:\n",
    "                    used[a]=1\n",
    "                    dfs2(a,p+price[a])\n",
    "                    used[a]=0\n",
    "        if n==2:\n",
    "            return max(price)\n",
    "        maxpr=0\n",
    "        root1=0\n",
    "        root2=0\n",
    "        arr=[[] for _ in range(n)]\n",
    "        used=[0]*n\n",
    "        dis=[0]*n\n",
    "        for e in edges:\n",
    "            arr[e[0]].append(e[1])\n",
    "            arr[e[1]].append(e[0])\n",
    "        used[0]=1\n",
    "        dfs1(0,price[0])\n",
    "        used[0]=0\n",
    "        root2=root1\n",
    "        maxpr=price[root2]\n",
    "        used[root2]=1\n",
    "        dfs1(root2,price[root2])\n",
    "        used[root2]=0\n",
    "        used[root1]=1\n",
    "        dfs2(root1,price[root1])\n",
    "        used[root1]=0\n",
    "        used[root2]=1\n",
    "        dfs2(root2,price[root2])\n",
    "        used[root2]=0\n",
    "        maxpr=0\n",
    "        for i in range(n):\n",
    "            if len(arr[i])==1:\n",
    "                maxpr=max(maxpr,dis[arr[i][0]])\n",
    "        return maxpr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        def dfs(u, fa, d):\n",
    "            if fa == -1: d[u] = price[u]\n",
    "            s, idx = 0, u\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                d[v] = d[u] + price[v]\n",
    "                s1, x = dfs(v, u, d)\n",
    "                if s < s1: s, idx = s1, x\n",
    "            return s + price[u], idx\n",
    "        \n",
    "        ds, dt = [0] * n, [0] * n\n",
    "        t = dfs(dfs(0, -1, ds)[1], -1, ds)[1]\n",
    "        dfs(t,-1,dt)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, max(ds[i],dt[i]) - price[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        if n == 1:return 0\n",
    "        has = [[] for _ in range(n)]\n",
    "        for i,j in edges:\n",
    "            has[i].append(j)\n",
    "            has[j].append(i)\n",
    "        self.ans = 0\n",
    "        def back(node,pre):\n",
    "            nums = [[0,0]]\n",
    "            for i in has[node]:\n",
    "                if i == pre:continue\n",
    "                nums.append(back(i,node))\n",
    "            a = b = 0\n",
    "            for i,j in nums:\n",
    "                if len(has[node]) == 1:\n",
    "                    self.ans = max(self.ans,price[node]+i,j)\n",
    "                else:\n",
    "                    self.ans = max(self.ans,max(i+b,a+j)+price[node])\n",
    "                a = max(a,i)\n",
    "                b = max(b,j)\n",
    "            if len(has[node]) == 1:return (0,price[node])\n",
    "            return (a+price[node],b+price[node])\n",
    "        back(0,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        # 以节点x为根，求最大的 最大路径和-prices[x]\n",
    "        # 最长路径一定是从叶子节点到叶子节点（度为1的节点）\n",
    "        # 找到任意一个度不为1的节点，然后以它为根，求出以每个节点为最高点的答案\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return max(price)\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "        for root in range(n):\n",
    "            if deg[root] > 1:\n",
    "                break\n",
    "        # print('root', root)\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(pa, x):\n",
    "            # 返回以x往下的最长路径，及去起始点最长子路\n",
    "            if deg[x] == 1:\n",
    "                return price[x], 0\n",
    "            pathes = []\n",
    "            sub_pathes = []\n",
    "            max_price = -1\n",
    "            max_sub_price = -1\n",
    "            for y in g[x]:\n",
    "                if y != pa:\n",
    "                    p, sp = dfs(x, y)\n",
    "                    pathes.append((p, y))\n",
    "                    sub_pathes.append((sp, y))\n",
    "                    if p > max_price:\n",
    "                        max_price = p\n",
    "                    if sp > max_sub_price:\n",
    "                        max_sub_price = sp\n",
    "            # print('x', x, 'p, s', (max_price, max_start), '(sp, ss)', (max_sub_price, max_sub_start))\n",
    "            # 计算以x为最高点的答案，要从结果里面选一个\n",
    "            if (pa == -1 and deg[x] >= 2) or deg[x] > 2:\n",
    "                nonlocal ans\n",
    "                # has more than 2 children\n",
    "                pathes.sort(reverse=True)\n",
    "                sub_pathes.sort(reverse=True)\n",
    "                # 必有一臂为最长path，或者最长sub_path\n",
    "                if pathes[0][1] != sub_pathes[0][1]:\n",
    "                    ans = max(ans, price[x] + pathes[0][0] + sub_pathes[0][0])\n",
    "                else:\n",
    "                    ans = max(ans, price[x] + pathes[0][0] + sub_pathes[1][0])\n",
    "                    ans = max(ans, price[x] + pathes[1][0] + sub_pathes[0][0])            \n",
    "            \n",
    "            return price[x] + max_price, price[x] + max_sub_price\n",
    "    \n",
    "        dfs(-1, root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        ed=[[] for i in range(n)]\n",
    "        for a,b in edges:\n",
    "            ed[a].append(b)\n",
    "            ed[b].append(a)\n",
    "        \n",
    "        scores=[0 for i in range(n)]\n",
    "        def dfs(cur,last):\n",
    "            score=price[cur]\n",
    "            maxx=0\n",
    "            for ne in ed[cur]:\n",
    "                if ne!=last:\n",
    "                    maxx=max(maxx,dfs(ne,cur))\n",
    "            score+=maxx\n",
    "            scores[cur]=score\n",
    "            return score\n",
    "        \n",
    "        for t in ed[0]:\n",
    "            dfs(t,0)\n",
    "        ans=max(scores)\n",
    "        \n",
    "        def dfs2(cur,last,val):\n",
    "            nonlocal ans\n",
    "            ans=max(ans,val)\n",
    "            \n",
    "            others=[]\n",
    "            for ne in ed[cur]:\n",
    "                if ne!=last:\n",
    "                    others.append((scores[ne],ne))\n",
    "            others.sort(reverse=True)\n",
    "            for ne in ed[cur]:\n",
    "                if ne!=last:\n",
    "                    for v,i in others:\n",
    "                        if i!=ne:\n",
    "                            dfs2(ne,cur,price[cur]+max(v,val))\n",
    "                            break\n",
    "                    else:\n",
    "                        dfs2(ne,cur,price[cur]+val)\n",
    "        \n",
    "        \n",
    "        dfs2(0,-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            a, b = e\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        # 换根dp => 从一个已知节点推导相连节点的大小\n",
    "        # f0表示以0为根的树上 各个节点的路径最大值\n",
    "        f0, f = [0] * n, [0] * n\n",
    "        \n",
    "        # 第一次dfs 求出0为根的路径最大值\n",
    "        def dfs1(u, p):\n",
    "            cur_mx = 0\n",
    "            for v in g[u]:\n",
    "                if v == p: continue\n",
    "                # 子树路径最大值\n",
    "                dfs1(v, u)\n",
    "                cur_mx = max(cur_mx, f0[v])\n",
    "                \n",
    "            f0[u] = cur_mx + price[u]\n",
    "        \n",
    "        # 第二次dfs 求转移\n",
    "        # f0这里会被动态修改 以表示换根后的状态\n",
    "        def dfs2(u, p):\n",
    "            #       p\n",
    "            #       |\n",
    "            #       u \n",
    "            #     /  |\n",
    "            #   v1, v2, ...\n",
    "            \n",
    "            # 统计子树中路径最大值, 次大值\n",
    "            m1, m2 = 0, 0\n",
    "            for v in g[u]:\n",
    "                # 注意不要写 v == p: continue (把父节点更新给丢了...)\n",
    "                # u为根 子树节点的路径最大值m1, 次大值m2\n",
    "                if f0[v] > m1:\n",
    "                    m2 = m1\n",
    "                    m1 = f0[v]\n",
    "                elif f0[v] > m2:\n",
    "                    m2 = f0[v]\n",
    "            \n",
    "            # 换根后的 当前路径最大值 可能的变化\n",
    "            f[u] = m1 + price[u]\n",
    "\n",
    "            # u -> v转移\n",
    "            for v in g[u]:\n",
    "                if v == p: continue\n",
    "                \n",
    "                # v是u的最大值路径子树节点 -> 去掉并且加上次大值 -> v变成根的情况(只关系u,v节点)\n",
    "                if f0[v] == m1:\n",
    "                    f0[u] = m2 + price[u]\n",
    "                else:\n",
    "                    # 没有影响 -> 继续使用最大子树路径值 + u的节点值作为 u节点最大路径值\n",
    "                    f0[u] = m1 + price[u]\n",
    "                \n",
    "                dfs2(v, u)\n",
    "\n",
    "        dfs1(0, -1)\n",
    "\n",
    "        dfs2(0, -1)\n",
    "\n",
    "        for u in range(n):\n",
    "            f[u] -= price[u]\n",
    "\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        cost = [0]*n\n",
    "        m_node = [-1]*n\n",
    "        n_node = [-1]*n \n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        \n",
    "        def dfs(x):\n",
    "            vis[x] = 1\n",
    "            ans = 0\n",
    "            for y in g[x]:\n",
    "                if vis[y] == 0:\n",
    "                    tmp = dfs(y)\n",
    "                    ans = max(ans,tmp)\n",
    "            cost[x] = ans + price[x]\n",
    "            return ans + price[x]\n",
    "        \n",
    "        vis = [0]*n\n",
    "        dfs(0)\n",
    "\n",
    "\n",
    "        val = [0]*n\n",
    "        def dfs1(x,p):\n",
    "            max1,max2 = 0,0\n",
    "            for y in g[x]:\n",
    "                if cost[y] > max1:\n",
    "                    max1,max2 = cost[y],max1\n",
    "                elif cost[y] > max2:\n",
    "                    max2 = cost[y]\n",
    "            val[x] = max1 + price[x]\n",
    "            for y in g[x]:\n",
    "                if y == p:\n",
    "                    continue\n",
    "                cost[x] = max1 + price[x] if max1 != cost[y] else max2 + price[x]\n",
    "                dfs1(y,x)\n",
    "        dfs1(0,-1)\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            val[i] -= price[i]\n",
    "        \n",
    "        return max(val)\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        ma=[0]*n\n",
    "        g=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfsl(k,pa,l):\n",
    "            ans=0\n",
    "            l+=price[k]\n",
    "            for nx in g[k]:\n",
    "                if nx==pa:continue\n",
    "                ans=max(ans,dfsl(nx,k,max(l,ans+price[k])))\n",
    "            ans+=price[k]\n",
    "            ma[k]=max(ma[k],ans,l)\n",
    "            return ans\n",
    "        def dfsr(k,pa,l):\n",
    "            ans=0\n",
    "            l+=price[k]\n",
    "            ma[k]=max(ma[k],l)\n",
    "            for j in range(len(g[k])-1,-1,-1):\n",
    "                if pa==g[k][j]:continue\n",
    "                ans=max(ans,dfsr(g[k][j],k,max(l,ans+price[k])))\n",
    "            ans+=price[k]\n",
    "            ma[k]=max(ma[k],ans,l)\n",
    "            return ans\n",
    "        dfsl(0,-1,0)\n",
    "        dfsr(0,-1,0)\n",
    "        return max(ma[i]-price[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        ma = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfsl(k, pa, l):\n",
    "            ans = 0\n",
    "            l += price[k]\n",
    "            for nx in g[k]:\n",
    "                if nx == pa: continue\n",
    "                ans = max(ans, dfsl(nx, k, max(l, ans + price[k])))\n",
    "            ans += price[k]\n",
    "            ma[k] = max(ma[k], ans, l)\n",
    "            return ans\n",
    "\n",
    "        def dfsr(k, pa, l):\n",
    "            ans = 0\n",
    "            l += price[k]\n",
    "            ma[k] = max(ma[k], l)\n",
    "            for j in range(len(g[k])-1, -1, -1):\n",
    "                if pa == g[k][j]: continue\n",
    "                ans = max(ans, dfsr(g[k][j], k, max(l, ans + price[k])))\n",
    "            ans += price[k]\n",
    "            ma[k] = max(ma[k], ans, l)\n",
    "            return ans\n",
    "\n",
    "        dfsl(0, -1, 0)\n",
    "        dfsr(0, -1, 0)\n",
    "        return max(ma[i] - price[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        def dfs1(u,f):\n",
    "            mx=0\n",
    "            for v in g[u]:\n",
    "                if v!=f:\n",
    "                    dfs1(v,u)\n",
    "                    mx=max(mx,maxprice[v])\n",
    "            maxprice[u]+=mx\n",
    "        maxprice=price[:]\n",
    "        dfs1(0,-1)\n",
    "        res=[0]*n\n",
    "        def dfs2(u,f):\n",
    "            fi=se=0\n",
    "            for v in g[u]:\n",
    "                if maxprice[v]>fi:\n",
    "                    se=fi\n",
    "                    fi=maxprice[v]\n",
    "                elif maxprice[v]>se:\n",
    "                    se=maxprice[v]\n",
    "            res[u]=fi+price[u]\n",
    "            for v in g[u]:\n",
    "                if v!=f:\n",
    "                    if maxprice[v]==fi:\n",
    "                        maxprice[u]=se+price[u]\n",
    "                    else:\n",
    "                        maxprice[u]=fi+price[u]\n",
    "                    dfs2(v,u)\n",
    "        dfs2(0,-1)\n",
    "        ans=0\n",
    "        for i,r in enumerate(res):\n",
    "            ans=max(ans,r-price[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(root, fa):\n",
    "            max1, max2 = price[root], 0\n",
    "            for e in g[root]:\n",
    "                if e == fa:\n",
    "                    continue\n",
    "                s1, s2 = dfs(e, root)\n",
    "                nonlocal ans\n",
    "                ans = max(ans, s1 + max2, s2 + max1)\n",
    "                max1 = max(max1, s1 + price[root])\n",
    "                max2 = max(max2, price[root] + s2)\n",
    "            return max1, max2\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        self.ans=0\n",
    "        def dfs(x,fa):\n",
    "            noleaf=0\n",
    "            withleaf=price[x]\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    a,b=dfs(y,x)\n",
    "                    self.ans=max(self.ans,a+withleaf,b+noleaf)\n",
    "                    noleaf=max(noleaf,a+price[x])\n",
    "                    withleaf=max(withleaf,b+price[x])\n",
    "            return noleaf,withleaf\n",
    "\n",
    "        dfs(0,-1)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            a, b = e\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        # 换根dp => 从一个已知节点推导相连节点的大小\n",
    "        # f0表示以0为根的树上 各个节点的路径最大值\n",
    "        f0, f = [0] * n, [0] * n\n",
    "        \n",
    "        # 第一次dfs 求出0为根的路径最大值\n",
    "        def dfs1(u, p):\n",
    "            cur_mx = 0\n",
    "            for v in g[u]:\n",
    "                if v == p: continue\n",
    "                # 子树路径最大值\n",
    "                dfs1(v, u)\n",
    "                cur_mx = max(cur_mx, f0[v])\n",
    "                \n",
    "            f0[u] = cur_mx + price[u]\n",
    "        \n",
    "        # 第二次dfs 求转移\n",
    "        # f0这里会被动态修改 以表示换根后的状态\n",
    "        def dfs2(u, p):\n",
    "            #       p\n",
    "            #       |\n",
    "            #       u \n",
    "            #     /  |\n",
    "            #   v1, v2, ...\n",
    "            \n",
    "            # 统计子树中路径最大值, 次大值\n",
    "            m1, m2 = 0, 0\n",
    "            for v in g[u]:\n",
    "                # 注意不要写 v == p: continue (把父节点更新给丢了...)\n",
    "                # u为根 子树节点的路径最大值m1, 次大值m2\n",
    "                if f0[v] > m1:\n",
    "                    m2 = m1\n",
    "                    m1 = f0[v]\n",
    "                elif f0[v] > m2:\n",
    "                    m2 = f0[v]\n",
    "            \n",
    "            # 换根后的 当前路径最大值 可能的变化\n",
    "            f[u] = m1 + price[u]\n",
    "\n",
    "            # u -> v转移\n",
    "            for v in g[u]:\n",
    "                if v == p: continue\n",
    "                \n",
    "                # v是u的最大值路径子树节点 -> 去掉并且加上次大值 -> v变成根的情况(只关系u,v节点)\n",
    "                if f0[v] == m1:\n",
    "                    f0[u] = m2 + price[u]\n",
    "                else:\n",
    "                    # 没有影响 -> 继续使用最大子树路径值 + u的节点值作为 u节点最大路径值\n",
    "                    f0[u] = m1 + price[u]\n",
    "                \n",
    "                dfs2(v, u)\n",
    "\n",
    "        dfs1(0, -1)\n",
    "\n",
    "        dfs2(0, -1)\n",
    "\n",
    "        for u in range(n):\n",
    "            f[u] -= price[u]\n",
    "\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "\n",
    "        edge_dict = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            edge_dict[x].append(y)\n",
    "            edge_dict[y].append(x)\n",
    "        \n",
    "        ans = 0\n",
    "        def DFS(x, parent):\n",
    "\n",
    "            nonlocal ans\n",
    "            \n",
    "            sx_leaf, sx_no_leaf = price[x], 0 \n",
    "\n",
    "            for y in edge_dict[x]:\n",
    "                if y==parent:\n",
    "                    continue\n",
    "                with_leaf, without_leaf = DFS(y,x)\n",
    "                ans = max(ans, sx_leaf+without_leaf, sx_no_leaf+with_leaf)\n",
    "                \n",
    "                sx_leaf = max(sx_leaf,with_leaf+price[x])\n",
    "                sx_no_leaf = max(sx_no_leaf, without_leaf+price[x])\n",
    "            return  sx_leaf, sx_no_leaf\n",
    "        \n",
    "        DFS(0,-1)\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        res = 0\n",
    "        def dfs(node, par):\n",
    "            nonlocal res \n",
    "            inc, exc = price[node], 0 \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                nxt = dfs(nei, node)\n",
    "                res = max(res, inc + nxt[1], exc + nxt[0])\n",
    "                inc = max(inc, nxt[0] + price[node])\n",
    "                exc = max(exc, nxt[1] + price[node])\n",
    "            return inc, exc\n",
    "        dfs(0, - 1)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        self.ans = 0\n",
    "        def f(u,fa):    \n",
    "            mv_w_leaf = p = price[u]\n",
    "            mv_wo_leaf = 0\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                cur_w_leaf, cur_wo_leaf = f(v,u)    \n",
    "                self.ans = max(self.ans, mv_w_leaf + cur_wo_leaf , mv_wo_leaf + cur_w_leaf )\n",
    "                mv_w_leaf = max(mv_w_leaf, cur_w_leaf+price[u])\n",
    "                mv_wo_leaf = max(mv_wo_leaf, cur_wo_leaf+price[u])\n",
    "            return mv_w_leaf, mv_wo_leaf\n",
    "        f(0,-1)\n",
    "        return self.ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。\n",
    "\n",
    "# 每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。\n",
    "\n",
    "# 一条路径的 价值和 是这条路径上所有节点的价值之和。\n",
    "\n",
    "# 你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。\n",
    "\n",
    "# 请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。\n",
    "\n",
    "\n",
    "from typing import Callable, Generic, List, TypeVar\n",
    "\n",
    "T = TypeVar(\"T\")\n",
    "\n",
    "E = Callable[[int], T]\n",
    "\"\"\"identify element of op, and answer of leaf\"\"\"\n",
    "\n",
    "Op = Callable[[T, T], T]\n",
    "\"\"\"merge value of child node\"\"\"\n",
    "\n",
    "Composition = Callable[[T, int, int, int], T]\n",
    "\"\"\"return value from child node to parent node\"\"\"\n",
    "\n",
    "\n",
    "class Rerooting(Generic[T]):\n",
    "    __slots__ = (\"g\", \"_n\", \"_decrement\", \"_root\", \"_parent\", \"_order\")\n",
    "\n",
    "    def __init__(self, n: int, decrement: int = 0):\n",
    "        \"\"\"\n",
    "        n: 节点个数\n",
    "        decrement: 节点id可能需要偏移 (1-indexed则-1, 0-indexed则0)\n",
    "        \"\"\"\n",
    "        self.g = [[] for _ in range(n)]\n",
    "        self._n = n\n",
    "        self._decrement = decrement\n",
    "        self._root = None  # 一开始的根\n",
    "\n",
    "    def addEdge(self, u: int, v: int):\n",
    "        \"\"\"\n",
    "        无向树加边\n",
    "        \"\"\"\n",
    "        u -= self._decrement\n",
    "        v -= self._decrement\n",
    "        self.g[u].append(v)\n",
    "        self.g[v].append(u)\n",
    "\n",
    "    def rerooting(\n",
    "            self, e: E[\"T\"], op: Op[\"T\"], composition: Composition[\"T\"], root=0\n",
    "    ) -> List[\"T\"]:\n",
    "        \"\"\"\n",
    "        - e: 初始化每个节点的价值\n",
    "          (root) -> res\n",
    "          mergeの単位元\n",
    "          例:求最长路径 e=0\n",
    "\n",
    "        - op: 两个子树答案如何组合或取舍\n",
    "          (childRes1,childRes2) -> newRes\n",
    "          例:求最长路径 return max(childRes1,childRes2)\n",
    "\n",
    "        - composition: 知道子子树答案和节点值，如何更新子树答案\n",
    "          (from_res,fa,u,use_fa) -> new_res\n",
    "          use_fa: 0表示用u更新fa的dp1,1表示用fa更新u的dp2          \n",
    "          例:最长路径return from_res+1\n",
    "\n",
    "        - root: 可能要设置初始根，默认是0\n",
    "\n",
    "        <概要>\n",
    "        1. rootを根としてまず一度木構造をbfsで求める 多くの場合rootは任意 (0)\n",
    "        2. 自身の部分木のdpの値をdp1に、自身を含まない兄弟のdpの値のmergeをdp2に入れる\n",
    "          木構造が定まっていることからこれが効率的に求められる。 葉側からボトムアップに実行する\n",
    "        3. 任意の頂点を新たに根にしたとき、部分木は\n",
    "          ①元の部分木 ②兄弟を親とした部分木 ③元の親を親とした(元の根の方向に伸びる)部分木の三つに分かれる。\n",
    "          ①はstep2のdp1であり、かつdp2はstep3において、②から②と③をmergeした値へと更新されているので\n",
    "          ②も③も分かっている。 根側からトップダウンに実行する(このことが上記の更新において重要)\n",
    "\n",
    "        計算量 O(|V|) (Vは頂点数)\n",
    "        参照 https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e\n",
    "        \"\"\"\n",
    "        # step1\n",
    "        root -= self._decrement\n",
    "        assert 0 <= root < self._n\n",
    "        self._root = root\n",
    "        g = self.g\n",
    "        _fas = self._parent = [-1] * self._n  # 记录每个节点的父节点\n",
    "        _order = self._order = [root]  # 用栈遍历记录dfs序\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            u = stack.pop()\n",
    "            for v in g[u]:\n",
    "                if v == _fas[u]:\n",
    "                    continue\n",
    "                _fas[v] = u\n",
    "                _order.append(v)\n",
    "                stack.append(v)\n",
    "\n",
    "        # step2\n",
    "        dp1 = [e(i) for i in range(self._n)]  # !子树部分的dp值,假设u是当前子树的根，vs是第一层儿子(它的非父邻居)，则dp1[u]=op(dp1(vs))\n",
    "        dp2 = [e(i) for i in\n",
    "               range(self._n)]  # !非子树部分的dp值,假设u是当前子树的根，vs={v1,v2..vi..}是第一层儿子(它的非父邻居),则dp2[vi]=op(dp1(vs-vi)),即他的兄弟们\n",
    "        for u in _order[::-1]:  # 从下往上拓扑序dp\n",
    "            res = e(u)\n",
    "            for v in g[u]:\n",
    "                if _fas[u] == v:\n",
    "                    continue\n",
    "                dp2[v] = res\n",
    "                res = op(res, composition(dp1[v], u, v, 0))  # op从下往上更新dp1\n",
    "            # 由于最大可能在后边，因此还得倒序来一遍\n",
    "            res = e(u)\n",
    "            for v in g[u][::-1]:\n",
    "                if _fas[u] == v:\n",
    "                    continue\n",
    "                dp2[v] = op(res, dp2[v])\n",
    "                res = op(res, composition(dp1[v], u, v, 0))\n",
    "            dp1[u] = res\n",
    "\n",
    "        # step3 自顶向下计算每个节点作为根时的dp1，dp2的含义变更为:dp2[u]为u的兄弟+父。这样对v来说dp1[v] = op(dp1[u],dp1[v])\n",
    "        for newRoot in _order[1:]:  #\n",
    "            parent = _fas[newRoot]\n",
    "            dp2[newRoot] = composition(\n",
    "                op(dp2[newRoot], dp2[parent]), parent, newRoot, 1\n",
    "            )  # op从上往下更新dp2\n",
    "            dp1[newRoot] = op(dp1[newRoot], dp2[newRoot])\n",
    "        return dp1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "\n",
    "        def e(root: int) -> int:\n",
    "            # mergeの単位元\n",
    "            # 例:最も遠い点までの距離を求める場合 e=0\n",
    "            return 0\n",
    "\n",
    "        def op(child_res1: int, child_res2: int) -> int:\n",
    "            # 如何组合/取舍两个子树的答案\n",
    "            # 例：求最长路径 return max(childRes1,childRes2)\n",
    "            return max(child_res1, child_res2)\n",
    "\n",
    "        def composition(from_res: int, fa: int, u: int, use_fa: int = 0) -> int:\n",
    "            # 知道子树的每个子树和节点值，如何更新子树答案;\n",
    "            # 例子:求最长路径 return from_res+1\n",
    "            if use_fa == 0:  # cur -> parent\n",
    "                return from_res + price[u]\n",
    "            return from_res + price[fa]\n",
    "\n",
    "        R = Rerooting(n)\n",
    "        for u, v in edges:\n",
    "            R.addEdge(u, v)\n",
    "        res = R.rerooting(e, op, composition)\n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def bfs(x: int):\n",
    "            last = 0\n",
    "            dis = [0] * n\n",
    "            vis = [False] * n\n",
    "            dis[x] = price[x]\n",
    "            vis[x] = True\n",
    "            q = deque([x])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                if dis[x] > dis[last]:\n",
    "                    last = x \n",
    "                for y in g[x]:\n",
    "                    if vis[y]: continue\n",
    "                    q.append(y)\n",
    "                    vis[y] = True\n",
    "                    dis[y] = dis[x] + price[y]\n",
    "            return last, dis\n",
    "\n",
    "        s, _ = bfs(0)\n",
    "        t, dis1 = bfs(s)\n",
    "        _, dis2 = bfs(t)\n",
    "        return max(max(dis1[i], dis2[i]) - price[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "inf = 2 ** 31\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        root = 0\n",
    "        adj = [[] for _ in range(n)]\n",
    "        children = [[] for _ in range(n)]\n",
    "\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        \n",
    "        visited = [False] * n\n",
    "        isleaf = [True] * n\n",
    "        def visit1(node: int) -> None:\n",
    "            for u in adj[node]:\n",
    "                if not visited[u]:\n",
    "                    visited[u] = True\n",
    "                    isleaf[node] = False\n",
    "                    children[node].append(u)\n",
    "                    visit1(u)\n",
    "\n",
    "        visited[root] = True\n",
    "        visit1(root)\n",
    "\n",
    "        #print(children)\n",
    "        #print(isleaf)\n",
    "\n",
    "        def visit(node: int) -> Tuple[Tuple[int, int], Tuple[int, int], int]:\n",
    "            # maxvalpath, leafval\n",
    "            # maxvalpathwithoutleafval, leafval\n",
    "            # maxval\n",
    "            if isleaf[node]:\n",
    "                return ((price[node], price[node]), (0, price[node]), 0)\n",
    "            else:\n",
    "                reta = (0, 0)\n",
    "                retb = (-inf, 0)\n",
    "                retc = 0\n",
    "                for child in children[node]:\n",
    "                    a, b, c = visit(child)\n",
    "\n",
    "                    retc = max(retc, b[0] + reta[0] + price[node])\n",
    "                    retc = max(retc, a[0] + retb[0] + price[node])\n",
    "                    retc = max(retc, a[0])\n",
    "\n",
    "                    if a[0] > reta[0] or (a[0] == reta[0] and a[1] < reta[1]):\n",
    "                        reta = a\n",
    "                    \n",
    "                    if b[0] > retb[0] or (b[0] == retb[0] and b[1] < retb[1]):\n",
    "                        retb = b\n",
    "                    \n",
    "                    if c > retc:\n",
    "                        retc = c\n",
    "\n",
    "                reta = (reta[0] + price[node], reta[1])\n",
    "                retb = (retb[0] + price[node], retb[1])\n",
    "                retc = max([retc, reta[0] - reta[1], retb[0]])\n",
    "                #print(node, reta, retb, retc)\n",
    "                return reta, retb, retc\n",
    "        ret = visit(root)\n",
    "        #print(ret)\n",
    "        return ret[2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        # 换根dp\n",
    "        # 价值最小的路径就是根自己\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = [0] * n # 最终结果，每个节点作为根的开销！\n",
    "        dp = [0] * n\n",
    "        # dp[i]: 以i为root的子树，价值和最大的一条路径价值\n",
    "        def dfs1(u, f):\n",
    "            tmp = price[u]\n",
    "            dp[u] = tmp\n",
    "            for v in g[u]:\n",
    "                if v == f:\n",
    "                    continue\n",
    "                dfs1(v, u)\n",
    "                dp[u] = max(dp[u], tmp + dp[v])\n",
    "        dfs1(0, -1)\n",
    "        #print(dp)\n",
    "        from sortedcontainers import SortedList\n",
    "        def dfs2(u, f): # 换根，获取ans\n",
    "            #print(u, f)\n",
    "            #print(dp)\n",
    "            # 当前根为u\n",
    "            ans[u] = dp[u] - price[u]\n",
    "            # 要记录u的不要邻居v的最大价值\n",
    "            stl = SortedList()\n",
    "            for v in g[u]:\n",
    "                stl.add(dp[v])\n",
    "            for v in g[u]:\n",
    "                if v == f:\n",
    "                    continue\n",
    "                pu, pv = dp[u], dp[v]\n",
    "                stl.remove(pv)\n",
    "                if len(stl) == 0:\n",
    "                    dp[u] = price[u]\n",
    "                    dp[v] = max(dp[v], dp[u] + price[v])\n",
    "                else: # u可以连除了v的其他子树\n",
    "                    dp[u] = stl[-1] + price[u]\n",
    "                    dp[v] = max(dp[v], dp[u] + price[v])\n",
    "                    #print(u, v, dp[u], dp[v])\n",
    "                dfs2(v, u)\n",
    "                # 回溯\n",
    "                stl.add(pv)\n",
    "                dp[u] = pu\n",
    "                dp[v] = pv\n",
    "        dfs2(0, -1)\n",
    "        #print(ans)\n",
    "        return max(ans)\n",
    "                \n",
    "# sol = Solution()\n",
    "# sol.maxOutput(100000, [[0, i] for i in range(1, 100000)], [1] * 100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "\n",
    "        def dfs(x, fa):\n",
    "            res = [0, 0]\n",
    "            for y in dct[x]:\n",
    "                if y != fa:\n",
    "                    nex = dfs(y, x)\n",
    "                    nex[0] += price[y]\n",
    "                    nex[1] += price[y]\n",
    "                    for a in nex[:1]:\n",
    "                        if a >= res[0]:\n",
    "                            res = [a, res[0]]\n",
    "                        elif a >= res[1]:\n",
    "                            res[1] = a\n",
    "            sub[x] = res[:]\n",
    "            return res\n",
    "\n",
    "        sub = [[0, 0] for _ in range(n)]\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def check(x, fa, pre):\n",
    "            nonlocal ans\n",
    "            if pre > ans:\n",
    "                ans = pre\n",
    "            for a in sub[x]:\n",
    "                if a > ans:\n",
    "                    ans = a\n",
    "            x1, x2 = sub[x]\n",
    "            for y in dct[x]:\n",
    "                if y != fa:\n",
    "                    b = x1 if sub[y][0] + price[y] != x1 else x2\n",
    "                    b = b if b > pre else pre\n",
    "                    check(y, x, b+price[x])\n",
    "            return\n",
    "\n",
    "        check(0, -1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        res=0\n",
    "        ans=0\n",
    "        ad={i:[] for i in range(n)}\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "        visited=[0]*n\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            maxs1=p=price[x]\n",
    "            maxs2=0\n",
    "            for nex in ad[x]:\n",
    "                if nex==fa:\n",
    "                    continue\n",
    "                s1,s2=dfs(nex,x)\n",
    "                ans=max(ans,maxs1+s2,maxs2+s1)\n",
    "                maxs1=max(s1+p,maxs1)\n",
    "                maxs2=max(s2+p,maxs2)\n",
    "\n",
    "            return maxs1,maxs2\n",
    "        dfs(0,-1)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Rerooting:\n",
    "    def __init__(self, n: int, decrement: int = 0):\n",
    "\n",
    "        self.n = n\n",
    "        self.adj = [[] for _ in range(n)]\n",
    "        self.root = None\n",
    "        self.decrement = decrement\n",
    "\n",
    "    def add_edge(self, u: int, v: int):\n",
    "\n",
    "        u -= self.decrement\n",
    "        v -= self.decrement\n",
    "        self.adj[u].append(v)\n",
    "        self.adj[v].append(u)\n",
    "\n",
    "    def rerooting(self, op, merge, e, root: int = 0) -> list:\n",
    "\n",
    "        root -= self.decrement\n",
    "        assert 0 <= root < self.n\n",
    "        self.root = root\n",
    "        self.parent = [-1] * self.n\n",
    "        self.order = [root]\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            from_node = stack.pop()\n",
    "            for to_node in self.adj[from_node]:\n",
    "                if to_node == self.parent[from_node]:\n",
    "                    continue\n",
    "                self.parent[to_node] = from_node\n",
    "                self.order.append(to_node)\n",
    "                stack.append(to_node)\n",
    "\n",
    "        dp1 = [e] * self.n\n",
    "        dp2 = [e] * self.n\n",
    "        for from_node in self.order[::-1]:\n",
    "            t = e\n",
    "            for to_node in self.adj[from_node]:\n",
    "                if self.parent[from_node] == to_node:\n",
    "                    continue\n",
    "                dp2[to_node] = t\n",
    "                t = merge(t, op(dp1[to_node], from_node, to_node))\n",
    "            t = e\n",
    "            for to_node in self.adj[from_node][::-1]:\n",
    "                if self.parent[from_node] == to_node:\n",
    "                    continue\n",
    "                dp2[to_node] = merge(t, dp2[to_node])\n",
    "                t = merge(t, op(dp1[to_node], from_node, to_node))\n",
    "            dp1[from_node] = t\n",
    "\n",
    "        for new_root in self.order[1:]:\n",
    "            par = self.parent[new_root]\n",
    "            dp2[new_root] = op(merge(dp2[new_root], dp2[par]), new_root, par)\n",
    "            dp1[new_root] = merge(dp1[new_root], dp2[new_root])\n",
    "        return dp1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        T = Rerooting(n, 0)\n",
    "        for u, v in edges:\n",
    "            T.add_edge(u, v)\n",
    "\n",
    "        def op(dp_v, u, v):\n",
    "\n",
    "            return dp_v + price[v]\n",
    "\n",
    "        def merge(dp_pu, dp_pv):\n",
    "\n",
    "            return max(dp_pu, dp_pv)\n",
    "\n",
    "        e = 0\n",
    "        dp = T.rerooting(op=op, merge=merge, e=e, root=0)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        self.ans = 0\n",
    "        dp = [0] * n\n",
    "        def f(u,fa):\n",
    "            maxv = 0\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                cur = f(v,u)\n",
    "                self.ans = max(self.ans, cur)\n",
    "                maxv= max(maxv, cur)\n",
    "            dp[u] =  maxv + price[u]\n",
    "            return dp[u]\n",
    "        f(0,-1)\n",
    "        def dfs(u, fa, pre):\n",
    "            self.ans = max(self.ans, pre)\n",
    "            maxv1 = maxv2 = 0\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                if maxv1 < dp[v]:\n",
    "                    maxv2 = maxv1\n",
    "                    maxv1 = dp[v]\n",
    "                elif maxv2< dp[v]:\n",
    "                    maxv2 = dp[v]\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                if maxv1 == dp[v]:\n",
    "                    dfs(v, u, max(pre, maxv2)+ price[u])\n",
    "                else:\n",
    "                    dfs(v, u, max(pre, maxv1)+ price[u])\n",
    "        dfs(0,-1,0)\n",
    "        return self.ans\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g =defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        self.ans = 0    \n",
    "        f = [0] * n\n",
    "        \n",
    "        def dfs(u, fa):\n",
    "            maxv = 0\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                cur = dfs(v,u)\n",
    "                self.ans = max(self.ans, cur)\n",
    "                maxv = max(maxv, cur)\n",
    "            f[u] = maxv + price[u]\n",
    "            return f[u]\n",
    "        def dfs2(u,fa,pre):\n",
    "            self.ans = max(self.ans, pre)\n",
    "            maxv1 = maxv2 =0\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                if maxv1 < f[v]:\n",
    "                    maxv2 = maxv1\n",
    "                    maxv1 = f[v]\n",
    "                elif maxv2 < f[v]:\n",
    "                    maxv2 = f[v]\n",
    "            for v in g[u]:        \n",
    "                if v == fa: continue\n",
    "                if f[v] == maxv1:\n",
    "                    dfs2(v,u, max(pre,maxv2) + price[u])\n",
    "                else:\n",
    "                    dfs2(v,u, max(pre,maxv1) + price[u])\n",
    "        dfs(0,-1)\n",
    "        dfs2(0,-1,0)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        f  = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def dfs(u,fa):\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                cur = dfs(v,u)\n",
    "                f[u] = max(f[u], cur)\n",
    "            self.ans = max(self.ans, f[u])\n",
    "            f[u] += price[u]\n",
    "            return f[u]\n",
    "        def dfs2(u, fa, pre):\n",
    "            self.ans = max(self.ans, pre)\n",
    "            maxv1, maxv2 = 0, 0\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                cur = f[v]\n",
    "                if maxv1 < cur:\n",
    "                    maxv2 = maxv1\n",
    "                    maxv1 = cur\n",
    "                elif maxv2 < cur:\n",
    "                    maxv2 = cur\n",
    "            for v in g[u]:\n",
    "                if v == fa: continue\n",
    "                if f[v] == maxv1:\n",
    "                    dfs2(v,u, max(pre, maxv2) + price[u])\n",
    "                else:\n",
    "                    dfs2(v,u, max(pre, maxv1) + price[u])\n",
    "        dfs(0, -1)\n",
    "        dfs2(0, -1, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        # f[u]: the maximum price sum rooted as u\n",
    "        f = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "\n",
    "        self.ans = 0\n",
    "        def dfs(u,fa):\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                cur = dfs(v, u)\n",
    "                f[u] = max(f[u], cur)\n",
    "            self.ans = max(self.ans, f[u])\n",
    "            f[u] += price[u]\n",
    "            return f[u]\n",
    "        \n",
    "        def dfs2(u,fa, pre):\n",
    "            self.ans = max(self.ans, pre)\n",
    "            maxv1 = maxv2 = 0\n",
    "            for v in g[u]:\n",
    "                if v== fa:\n",
    "                    continue\n",
    "                cur = f[v]\n",
    "                if maxv1 < cur:\n",
    "                    maxv2 = maxv1\n",
    "                    maxv1 = cur\n",
    "                elif maxv2 < cur:    \n",
    "                    maxv2 = cur\n",
    "            for v in g[u]:        \n",
    "                if v == fa: continue\n",
    "                if f[v] == maxv1:\n",
    "                    dfs2(v,u, max(pre, maxv2) + price[u])\n",
    "                else:\n",
    "                    dfs2(v,u, max(pre, maxv1) + price[u])\n",
    "        dfs(0,-1)\n",
    "        dfs2(0,-1,0)\n",
    "        return self.ans\n",
    "\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "\n",
    "        graph=[[] for _ in range(n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            graph[edges[i][0]].append(edges[i][1])\n",
    "            graph[edges[i][1]].append(edges[i][0])\n",
    "\n",
    "        from heapq import heappush,heappop\n",
    "        self.res=0\n",
    "        visited=set()\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            withLeaf,withOutLeaf=0,0\n",
    "            count=0\n",
    "            wlList,wolList=[],[]\n",
    "            for c in graph[node]:\n",
    "                if c not in visited:\n",
    "                    count+=1\n",
    "                    wl,wol=dfs(c)\n",
    "                    heappush(wlList,[-wl,c])\n",
    "                    heappush(wolList,[-wol,c])\n",
    "                    withLeaf=max(withLeaf,wl)\n",
    "                    withOutLeaf=max(withOutLeaf,wol)\n",
    "            if count==0: return price[node],0\n",
    "            elif count==1: \n",
    "                self.res=max(self.res,withLeaf,price[node]+withOutLeaf)\n",
    "                return withLeaf+price[node],withOutLeaf+price[node]\n",
    "            else:\n",
    "                wl0=heappop(wlList)\n",
    "                wol0=heappop(wolList)\n",
    "                if wl0[1]!=wol0[1]: self.res=max(self.res,-wl0[0]-wol0[0]+price[node])\n",
    "                else:\n",
    "                    wl1=heappop(wlList)\n",
    "                    wol1=heappop(wolList)\n",
    "                    self.res=max(self.res,-wl0[0]-wol1[0]+price[node],-wl1[0]-wol0[0]+price[node])\n",
    "                return withLeaf+price[node],withOutLeaf+price[node]\n",
    "\n",
    "        dfs(0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from random import randint\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。\n",
    "\n",
    "# 每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。\n",
    "\n",
    "# 一条路径的 价值和 是这条路径上所有节点的价值之和。\n",
    "\n",
    "# 你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。\n",
    "\n",
    "# 请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。\n",
    "\n",
    "\n",
    "from typing import Callable, Generic, List, TypeVar\n",
    "\n",
    "T = TypeVar(\"T\")\n",
    "\n",
    "\n",
    "E = Callable[[int], T]\n",
    "\"\"\"identify element of op, and answer of leaf\"\"\"\n",
    "\n",
    "Op = Callable[[T, T], T]\n",
    "\"\"\"merge value of child node\"\"\"\n",
    "\n",
    "Composition = Callable[[T, int, int, int], T]\n",
    "\"\"\"return value from child node to parent node\"\"\"\n",
    "\n",
    "\n",
    "class Rerooting(Generic[T]):\n",
    "\n",
    "    __slots__ = (\"adjList\", \"_n\", \"_decrement\", \"_root\", \"_parent\", \"_order\")\n",
    "\n",
    "    def __init__(self, n: int, decrement: int = 0):\n",
    "        \"\"\"\n",
    "        n: 頂点数\n",
    "        decrement: 頂点の値を減らす量 (1-indexedなら1, 0-indexedなら0)\n",
    "        \"\"\"\n",
    "        self.adjList = [[] for _ in range(n)]\n",
    "        self._n = n\n",
    "        self._decrement = decrement\n",
    "        self._root = None  # 一番最初に根とする頂点\n",
    "\n",
    "    def addEdge(self, u: int, v: int):\n",
    "        \"\"\"\n",
    "        u,v 間に無向辺を張る (u->v, v->u)\n",
    "        \"\"\"\n",
    "        u -= self._decrement\n",
    "        v -= self._decrement\n",
    "        self.adjList[u].append(v)\n",
    "        self.adjList[v].append(u)\n",
    "\n",
    "    def rerooting(self, e: E[\"T\"], op: Op[\"T\"], composition: Composition[\"T\"], root=0) -> List[\"T\"]:\n",
    "        \"\"\"\n",
    "        - e: 単位元\n",
    "          (root) -> res\n",
    "          mergeの単位元\n",
    "          例:最も遠い点までの距離を求める場合 e=0\n",
    "\n",
    "        - op: 子の値を親にマージする関数\n",
    "          (childRes1,childRes2) -> newRes\n",
    "          モノイドの性質を満たす演算を定義する それが全方位木DPをする条件\n",
    "          例:最も遠い点までの距離を求める場合 return max(childRes1,childRes2)\n",
    "\n",
    "        - composition: 頂点の値を更新する関数\n",
    "          (fromRes,parent,cur,direction) -> newRes\n",
    "          direction: 0表示用cur更新parent的dp1,1表示用parent更新cur的dp2\n",
    "          dpをmergeする前段階で実行する演算\n",
    "          例:最も遠い点までの距離を求める場合 return fromRes+1\n",
    "\n",
    "        - root: 根とする頂点\n",
    "\n",
    "        <概要>\n",
    "        1. rootを根としてまず一度木構造をbfsで求める 多くの場合rootは任意 (0)\n",
    "        2. 自身の部分木のdpの値をdp1に、自身を含まない兄弟のdpの値のmergeをdp2に入れる\n",
    "          木構造が定まっていることからこれが効率的に求められる。 葉側からボトムアップに実行する\n",
    "        3. 任意の頂点を新たに根にしたとき、部分木は\n",
    "          ①元の部分木 ②兄弟を親とした部分木 ③元の親を親とした(元の根の方向に伸びる)部分木の三つに分かれる。\n",
    "          ①はstep2のdp1であり、かつdp2はstep3において、②から②と③をmergeした値へと更新されているので\n",
    "          ②も③も分かっている。 根側からトップダウンに実行する(このことが上記の更新において重要)\n",
    "\n",
    "        計算量 O(|V|) (Vは頂点数)\n",
    "        参照 https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e\n",
    "        \"\"\"\n",
    "        # step1\n",
    "        root -= self._decrement\n",
    "        assert 0 <= root < self._n\n",
    "        self._root = root\n",
    "        self._parent = [-1] * self._n  # 親の番号を記録\n",
    "        self._order = [root]  # bfsの訪問順を記録 深さが広義単調増加している\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for next in self.adjList[cur]:\n",
    "                if next == self._parent[cur]:\n",
    "                    continue\n",
    "                self._parent[next] = cur\n",
    "                self._order.append(next)\n",
    "                stack.append(next)\n",
    "\n",
    "        # step2\n",
    "        dp1 = [e(i) for i in range(self._n)]  # !子树部分的dp值\n",
    "        dp2 = [e(i) for i in range(self._n)]  # !非子树部分的dp值\n",
    "        for cur in self._order[::-1]:  # 从下往上拓扑序dp\n",
    "            res = e(cur)\n",
    "            for next in self.adjList[cur]:\n",
    "                if self._parent[cur] == next:\n",
    "                    continue\n",
    "                dp2[next] = res\n",
    "                res = op(res, composition(dp1[next], cur, next, 0))  # op从下往上更新dp1\n",
    "            res = e(cur)\n",
    "            for next in self.adjList[cur][::-1]:\n",
    "                if self._parent[cur] == next:\n",
    "                    continue\n",
    "                dp2[next] = op(res, dp2[next])\n",
    "                res = op(res, composition(dp1[next], cur, next, 0))\n",
    "            dp1[cur] = res\n",
    "\n",
    "        # step3\n",
    "        for newRoot in self._order[1:]:  # 元の根に関するdp1は既に求まっている\n",
    "            parent = self._parent[newRoot]\n",
    "            dp2[newRoot] = composition(\n",
    "                op(dp2[newRoot], dp2[parent]), parent, newRoot, 1\n",
    "            )  # op从上往下更新dp2\n",
    "            dp1[newRoot] = op(dp1[newRoot], dp2[newRoot])\n",
    "        return dp1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        def e(root: int) -> int:\n",
    "            # mergeの単位元\n",
    "            # 例:最も遠い点までの距離を求める場合 e=0\n",
    "            return 0\n",
    "\n",
    "        def op(childRes1: int, childRes2: int) -> int:\n",
    "            # モノイドの性質を満たす演算を定義する それが全方位木DPをする条件\n",
    "            # 例:最も遠い点までの距離を求める場合 return max(childRes1,childRes2)\n",
    "            return max(childRes1, childRes2)\n",
    "\n",
    "        def composition(fromRes: int, parent: int, cur: int, direction: int) -> int:\n",
    "            # dpをmergeする前段階で実行する演算\n",
    "            # 例:最も遠い点までの距離を求める場合 return res+1\n",
    "            if direction == 0:  # cur -> parent\n",
    "                return fromRes + price[cur]\n",
    "            return fromRes + price[parent]\n",
    "\n",
    "        R = Rerooting(n)\n",
    "        for u, v in edges:\n",
    "            R.addEdge(u, v)\n",
    "        res = R.rerooting(e, op, composition)\n",
    "        return max(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        sub = [[0, 0] for _ in range(n)]\n",
    "        stack = [[0, -1]]\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            if i >= 0:\n",
    "                stack.append([~i, fa])\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:\n",
    "                        stack.append([j, i])\n",
    "            else:\n",
    "                i =~i\n",
    "                with_leaf = price[i]\n",
    "                with_out_leaf = 0\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:\n",
    "                        a, b = sub[j]\n",
    "                        ans = ans if ans > with_out_leaf + a else with_out_leaf + a\n",
    "                        ans = ans if ans > with_leaf + b else with_leaf + b\n",
    "                        with_leaf = with_leaf if with_leaf > a + price[i] else a + price[i]\n",
    "                        with_out_leaf = with_out_leaf if with_out_leaf > b + price[i] else b + price[i]\n",
    "                        \n",
    "                sub[i] = [with_leaf, with_out_leaf]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "\n",
    "        # dp[i][0] is the max value down path, dp[i][1] is the second max value down path, dp[i][2] is the max value up path\n",
    "        dp = [[0] * 3 for _ in range(n)]\n",
    "\n",
    "        def dfs1(x: int, pa: int) -> None:\n",
    "            dp[x][0] = p = price[x] # init max value down path\n",
    "\n",
    "            for v in g[x]:\n",
    "                if v == pa: continue\n",
    "                dfs1(v, x)\n",
    "                # update dp[x]\n",
    "                if dp[x][0] < dp[v][0] + p:\n",
    "                    dp[x][1] = dp[x][0]\n",
    "                    dp[x][0] = dp[v][0] + p\n",
    "                elif dp[x][1] < dp[v][0] + p:\n",
    "                    dp[x][1] = dp[v][0] + p\n",
    "        \n",
    "        def dfs2(x: int, pa: int) -> None:\n",
    "            for v in g[x]:\n",
    "                if v == pa: continue\n",
    "                # v is at the max value down path\n",
    "                if dp[v][0] + price[x] == dp[x][0]:\n",
    "                    dp[v][2] = max(dp[x][2], dp[x][1]) + price[v]\n",
    "                else:\n",
    "                    dp[v][2] = max(dp[x][2], dp[x][0]) + price[v]\n",
    "                dfs2(v, x)\n",
    "        \n",
    "        dfs1(0, -1)\n",
    "        dfs2(0, -1)\n",
    "        ans = 0\n",
    "        for i, [a, b, c] in enumerate(dp):\n",
    "            ans = max(ans, max(a, c) - price[i])\n",
    "        return ans\n",
    "                    \n",
    "            \n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        G = [set() for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            G[i].add(j)\n",
    "            G[j].add(i)\n",
    "\n",
    "        res = [0]\n",
    "        def dfs(i, pre = -1):\n",
    "            G[i].discard(pre)\n",
    "            if not G[i]:\n",
    "                return [price[i], 0]\n",
    "            first = [[0,0]]\n",
    "            second = [0]\n",
    "            for j in G[i]:\n",
    "                x,y = dfs(j, i)\n",
    "                first.append([x, y])\n",
    "                second.append(y)\n",
    "            first.sort()\n",
    "            second.sort()\n",
    "            if len(G[i]) == 1:\n",
    "                x,y = first[-1]\n",
    "                return [x + price[i], y + price[i]]\n",
    "            x, x2 = first[-1]\n",
    "            y = second[-1]\n",
    "            if x2 == y:\n",
    "                res[0] = max(res[0], x + second[-2] + price[i])\n",
    "                res[0] = max(res[0], first[-2][0] + x2 + price[i])\n",
    "            else:\n",
    "                res[0] = max(res[0], x + y + price[i])\n",
    "            return [x + price[i], y + price[i]]\n",
    "        x,y = dfs(0)\n",
    "        res[0] = max(res[0], y, x - price[0])\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        f = [[0]*3 for _ in range(n)]\n",
    "        son = [-1]*n\n",
    "        def dfs(u, pa):\n",
    "            f[u][0] = price[u]\n",
    "            for v in g[u]:\n",
    "                if v != pa:\n",
    "                    dfs(v, u)\n",
    "                    if f[u][0]<f[v][0]+price[u]:\n",
    "                        f[u][1] = f[u][0]\n",
    "                        f[u][0] = f[v][0]+price[u]\n",
    "                        son[u] = v\n",
    "                    elif f[u][1]<f[v][0]+price[u]:\n",
    "                        f[u][1] = f[v][0]+price[u]\n",
    "        def reroot(u, pa):\n",
    "            for v in g[u]:\n",
    "                if v != pa:\n",
    "                    if son[u] == v:\n",
    "                        f[v][2] = max(f[u][2], f[u][1])+price[v]\n",
    "                    else:\n",
    "                        f[v][2] = max(f[u][2], f[u][0])+price[v]\n",
    "                    reroot(v, u)\n",
    "        dfs(0, -1)\n",
    "        reroot(0, -1)\n",
    "        return max(max(f[u][0], f[u][2])-price[u] for u in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 12/58\n",
    "# from collections import defaultdict\n",
    "# class Solution:\n",
    "#     def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "#         g=defaultdict(list)\n",
    "#         for u,v in edges:\n",
    "#             g[u].append(v)\n",
    "#             g[v].append(u)\n",
    "\n",
    "#         self.ans=0\n",
    "#         def dfs(x,fa):\n",
    "#             mi=price[x]\n",
    "#             mx=price[x]\n",
    "#             for y in g[x]:\n",
    "#                 if y!=fa:\n",
    "#                     nxt=dfs(y,x)\n",
    "#                     cur=price[x]+nxt \n",
    "#                     self.ans=max(self.ans,cur-mi)\n",
    "#                     mx=max(mx,cur)\n",
    "#             return mx\n",
    "#         dfs(0,-1)\n",
    "#         return self.ans\n",
    "\n",
    "# 4\n",
    "# [[2,0],[0,1],[1,3]]\n",
    "# [2,3,1,1]  --- ans:6  测例不通过\n",
    "\n",
    "# ### pass rate 52/58\n",
    "### 这种思路不能全部通过的原因：可能存在多条线路是最大树直径值，但头节点的大小不一；我只计算了一条直径线路的去头节点值（不一定是全树的最大差值）\n",
    "# from collections import defaultdict\n",
    "# class Solution:\n",
    "#     def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "#         g=defaultdict(list)\n",
    "#         for u,v in edges:\n",
    "#             g[u].append(v)\n",
    "#             g[v].append(u)\n",
    "\n",
    "#         def dfs(x,fa,v):\n",
    "#             nonlocal mx,idx\n",
    "#             v+=price[x] ###确认每一轮都已经添加当前节点value（在比较mx之前）\n",
    "#             if v>mx:\n",
    "#                 mx=v\n",
    "#                 idx=x\n",
    "#             for y in g[x]:\n",
    "#                 if y!=fa:\n",
    "#                     dfs(y,x,v)\n",
    "#             return mx,idx\n",
    "\n",
    "#         mx,idx=0,-1\n",
    "#         _,node1=dfs(0,-1,0)\n",
    "#         mx,idx=0,-1\n",
    "#         v,node2=dfs(node1,-1,0)\n",
    "#         return v-min(price[node1],price[node2])\n",
    "\n",
    "\n",
    "# ### S-code\n",
    "# ###　Ｓ－ｃｏｄｅ\n",
    "# class Solution:\n",
    "#     def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "\n",
    "#         dct = [[] for _ in range(n)]\n",
    "#         for i, j in edges:\n",
    "#             dct[i].append(j)\n",
    "#             dct[j].append(i)\n",
    "        \n",
    "\n",
    "#         def dfs(i, fa):\n",
    "#             # 带叶子的路径和，与不带叶子的路径和\n",
    "#             nonlocal ans\n",
    "#             with_leaf = price[i]\n",
    "#             with_out_leaf = 0\n",
    "\n",
    "#             for j in dct[i]:\n",
    "#                 if j != fa:\n",
    "#                     a, b = dfs(j, i)\n",
    "#                     ans = ans if ans > with_out_leaf + a else with_out_leaf + a\n",
    "#                     ans = ans if ans > with_leaf + b else with_leaf + b\n",
    "#                     with_leaf = with_leaf  if with_leaf > a + price[i] else a+ price[i]\n",
    "#                     with_out_leaf = with_out_leaf if with_out_leaf  > b+ price[i] else b+ price[i]\n",
    "\n",
    "#             return with_leaf, with_out_leaf\n",
    "\n",
    "\n",
    "#         ans = 0\n",
    "#         dfs(0, -1)\n",
    "#         return ans\n",
    "\n",
    "# ### 示例代码复写\n",
    "# from collections import defaultdict\n",
    "# class Solution:\n",
    "#     def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "#         g=defaultdict(list)\n",
    "#         for u,v in edges:\n",
    "#             g[u].append(v)\n",
    "#             g[v].append(u)\n",
    "\n",
    "#         self.ans=0\n",
    "#         def dfs(x,fa):\n",
    "#             noleaf=0\n",
    "#             withleaf=price[x]\n",
    "#             for y in g[x]:\n",
    "#                 if y!=fa:\n",
    "#                     a,b=dfs(y,x)\n",
    "#                     self.ans=max(self.ans,a+withleaf,b+noleaf)\n",
    "#                     noleaf=max(noleaf,a+price[x])\n",
    "#                     withleaf=max(withleaf,b+price[x])\n",
    "#             return noleaf,withleaf\n",
    "\n",
    "#         dfs(0,-1)\n",
    "#         return self.ans\n",
    "\n",
    "# ### 灵茶山（1次DFS）\n",
    "# class Solution:\n",
    "#     def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "#         g = [[] for _ in range(n)]\n",
    "#         for x, y in edges:\n",
    "#             g[x].append(y)\n",
    "#             g[y].append(x)  # 建树\n",
    "\n",
    "#         ans = 0\n",
    "#         # 返回带叶子的最大路径和，不带叶子的最大路径和\n",
    "#         def dfs(x: int, fa: int) -> (int, int):\n",
    "#             nonlocal ans\n",
    "#             max_s1 = p = price[x]\n",
    "#             max_s2 = 0\n",
    "#             for y in g[x]:\n",
    "#                 if y == fa: continue\n",
    "#                 s1, s2 = dfs(y, x)\n",
    "#                 # 前面最大带叶子的路径和 + 当前不带叶子的路径和\n",
    "#                 # 前面最大不带叶子的路径和 + 当前带叶子的路径和\n",
    "#                 ans = max(ans, max_s1 + s2, max_s2 + s1)\n",
    "#                 max_s1 = max(max_s1, s1 + p)\n",
    "#                 max_s2 = max(max_s2, s2 + p)  # 这里加上 p 是因为 x 必然不是叶子\n",
    "#             return max_s1, max_s2\n",
    "#         dfs(0, -1)\n",
    "#         return ans\n",
    "\n",
    "\n",
    "# 自叶子向根的BFS：magical-agnesibu0\n",
    "# 链接：https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/solution/yan-du-you-xian-sou-suo-by-magical-agnes-m3yg/\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        # 建无向图\n",
    "        g = [set() for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        # 额外要记录的节点信息\n",
    "        s = price.copy()  # 当前最大带叶子的路径和\n",
    "        t = [0] * n  # 当前最大不带叶子的路径和\n",
    "        # 找出图中初始叶子节点，加入待处理的集合\n",
    "        # 此处以队列为例，但换成栈、堆、有序或无序的集合都没有问题\n",
    "        q = deque(i for i, d in enumerate(g) if len(d) == 1)### 队列添加所有叶子点\n",
    "        ans = 0\n",
    "        while q:\n",
    "            a = q.popleft()  # 叶子节点\n",
    "            b = g[a].pop()  # 取上级节点\n",
    "            g[b].remove(a)  # 并删除该边\n",
    "            # 记录b节点子树中经过b的最长路径\n",
    "            # 可能是当前最大不带叶子的路径和 + 当前带叶子的路径和\n",
    "            # 或者是当前最大带叶子的路径和 + 当前不带叶子的路径和\n",
    "            ans = max(ans, s[a] + t[b], t[a] + s[b])\n",
    "            # 记录b节点的最大带叶子的路径和和不带叶子的路径和\n",
    "            s[b] = max(s[b], s[a] + price[b])\n",
    "            t[b] = max(t[b], t[a] + price[b])\n",
    "            if len(g[b]) == 1:  # 上级节点变为叶子节点\n",
    "                q.append(b)  # 则上级节点入队\n",
    "            elif not g[b]:  # 因刚删的边，已仅剩最后一个孤立节点\n",
    "                break  # 则结束\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        G = [[] for i in range(n)] \n",
    "        for a,b in edges:\n",
    "            G[a].append(b) \n",
    "            G[b].append(a) \n",
    "        \n",
    "        down = [[0,0] for p in price]  \n",
    "        def dfs1(me,fa):\n",
    "            for son in G[me]:\n",
    "                if son == fa : continue \n",
    "                t = dfs1(son,me) \n",
    "                if t > down[me][0] : down[me] = [t,down[me][0]] \n",
    "                elif t > down[me][1]:  down[me] = [down[me][0],t] \n",
    "            return down[me][0] + price[me]\n",
    "        dfs1(0,-1)\n",
    "\n",
    "        up = [0]*n\n",
    "        def dfs2(me,fa):\n",
    "            for son in G[me]:\n",
    "                if son == fa : continue  \n",
    "                if down[son][0] + price[son] == down[me][0]:\n",
    "                    up[son] = max(down[me][1],up[me])+price[me] \n",
    "                else : \n",
    "                    up[son] = max(down[me][0],up[me])+price[me] \n",
    "                dfs2(son,me)\n",
    "        dfs2(0,-1) \n",
    "        return max(chain(up,*down))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 476 ms ... 77 % ... 66.8 MB ... 89 %\n",
    "        #  time: O(V+E)\n",
    "        # space: O(V+E)\n",
    "        \"\"\"\n",
    "        for any leaf1 and leaf2,\n",
    "        define f(leaf1, leaf2) = pathsum(leaf1,leaf2) - min(leaf1,leaf2)\n",
    "        find max(f)\n",
    "        \"\"\"\n",
    "        \n",
    "        def dfs(parent, node):                             # return node-started (maxpathsum, maxdiff), diff = pathsum - leafval\n",
    "            ps1, ps1node, ps2, ps2node = -1, -1, -1, -1    # max1 pathsum and its child-node, max2 pathsum and its child-node\n",
    "            df1, df1node, df2, df2node = -1, -1, -1, -1    # max1 diffval and its child-node, max2 diffval and its child-node\n",
    "            for child in conn[node]:\n",
    "                if child != parent:\n",
    "                    ps, df = dfs(node, child)              # child-started maxpathsum, child-started maxdiff\n",
    "                    if ps > ps1:\n",
    "                        ps1, ps1node, ps2, ps2node = ps, child, ps1, ps1node\n",
    "                    elif ps > ps2:\n",
    "                        ps2, ps2node = ps, child\n",
    "                    if df > df1:\n",
    "                        df1, df1node, df2, df2node = df, child, df1, df1node\n",
    "                    elif df > df2:\n",
    "                        df2, df2node = df, child\n",
    "            if ps1 == -1:\n",
    "                return price[node], 0\n",
    "            elif ps2 == -1:\n",
    "                if parent == -1:\n",
    "                    self.res = max(self.res, ps1, price[node] + df1)\n",
    "                return price[node] + ps1, price[node] + df1\n",
    "            elif ps1node != df1node:\n",
    "                self.res = max(self.res, ps1 + price[node] + df1)\n",
    "                return price[node] + ps1, price[node] + df1\n",
    "            else:\n",
    "                self.res = max(self.res, ps1 + price[node] + df2, ps2 + price[node] + df1)\n",
    "                return price[node] + ps1, price[node] + df1\n",
    "        \n",
    "        conn = collections.defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            conn[u].add(v)\n",
    "            conn[v].add(u)\n",
    "        self.res = 0\n",
    "        dfs(-1, 0)\n",
    "        return self.res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/env python3\n",
    "# -*- coding: utf-8 -*-\n",
    "# https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        return self.solution2(n, edges, price)\n",
    "\n",
    "    def solution1(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        \"\"\"DFS.\"\"\"\n",
    "        if n < 2:\n",
    "            return 0\n",
    "\n",
    "        degree = {}\n",
    "        nexts = defaultdict(set)  # 邻节点\n",
    "        for s, t in edges:\n",
    "            degree[s] = degree.get(s, 0) + 1\n",
    "            degree[t] = degree.get(t, 0) + 1\n",
    "            nexts[s].add(t)\n",
    "            nexts[t].add(s)\n",
    "\n",
    "        def dfs(s, pa):\n",
    "            \"\"\"s: 起始节点编号.\"\"\"\n",
    "            ans = 0\n",
    "            for n in nexts[s]:\n",
    "                if n == pa:\n",
    "                    continue\n",
    "                ans = max(ans, dfs(n, s))\n",
    "            return ans + price[s]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 从 i 出发的开销\n",
    "            if degree[i] != 1:\n",
    "                continue\n",
    "            ans = max(ans, dfs(i, None) - price[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def solution2(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        \"\"\"树形dp.\"\"\"\n",
    "        if n < 2:\n",
    "            return 0\n",
    "\n",
    "        nexts = defaultdict(set)  # 邻节点\n",
    "        for s, t in edges:\n",
    "            nexts[s].add(t)\n",
    "            nexts[t].add(s)\n",
    "\n",
    "        def dfs(i, pa):\n",
    "            \"\"\"返回带叶子结点的最大路径和，不带叶子结点的最大路径和, 以及答案.\"\"\"\n",
    "            m1, m2, ans = price[i], 0, 0\n",
    "            for n in nexts[i]:\n",
    "                if n == pa:\n",
    "                    continue\n",
    "                cm1, cm2, cans = dfs(n, i)\n",
    "                # m1 + cm2: 前面最大带叶子结点的路径和 + 当前不带叶子结点的路径和\n",
    "                # m2 + cm1: 前面最大不带叶子结点的路径和 + 当前带叶子结点的路径和\n",
    "                ans = max(ans, cans, m1 + cm2, m2 + cm1)\n",
    "                m1 = max(m1, cm1 + price[i])\n",
    "                m2 = max(m2, cm2 + price[i])\n",
    "            return m1, m2, ans\n",
    "\n",
    "        # 以 0 作为 root\n",
    "        return dfs(0, None)[2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        con = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            con[i].append(j)\n",
    "            con[j].append(i)\n",
    "        test = []\n",
    "        tov = []\n",
    "        vis = set()\n",
    "        p = [[0, 0] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            test.append(len(con[i]))\n",
    "            if test[-1] == 1:\n",
    "                tov.append(i)\n",
    "                p[i][0] = price[i]\n",
    "        ans = 0\n",
    "        while tov and len(vis) != n - 1:\n",
    "            x = tov.pop()\n",
    "            vis.add(x)\n",
    "            for i in con[x]:\n",
    "                if i in vis:\n",
    "                    continue\n",
    "                ans = max(ans, p[i][0] + p[x][1], p[i][1] + p[x][0])\n",
    "                p[i][0] = max(p[i][0], p[x][0] + price[i])\n",
    "                p[i][1] = max(p[i][1], p[x][1] + price[i])\n",
    "                test[i] -= 1\n",
    "                if test[i] == 1:\n",
    "                    tov.append(i)\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        # 建无向图\n",
    "        g = [set() for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        # 额外要记录的节点信息\n",
    "        s = price.copy()  # 当前最大带叶子的路径和\n",
    "        t = [0] * n  # 当前最大不带叶子的路径和\n",
    "        # 找出图中初始叶子节点，加入待处理的集合\n",
    "        # 此处以队列为例，但换成栈、堆、有序或无序的集合都没有问题\n",
    "        q = deque(i for i, d in enumerate(g) if len(d) == 1)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            a = q.popleft()  # 叶子节点\n",
    "            b = g[a].pop()  # 取上级节点\n",
    "            g[b].remove(a)  # 并删除该边\n",
    "            # 记录b节点子树中经过b的最长路径\n",
    "            # 可能是当前最大不带叶子的路径和 + 当前带叶子的路径和\n",
    "            # 或者是当前最大带叶子的路径和 + 当前不带叶子的路径和\n",
    "            ans = max(ans, s[a] + t[b], t[a] + s[b])\n",
    "            # 记录b节点的最大带叶子的路径和和不带叶子的路径和\n",
    "            s[b] = max(s[b], s[a] + price[b])\n",
    "            t[b] = max(t[b], t[a] + price[b])\n",
    "            if len(g[b]) == 1:  # 上级节点变为叶子节点\n",
    "                q.append(b)  # 则上级节点入队\n",
    "            elif not g[b]:  # 因刚删的边，已仅剩最后一个孤立节点\n",
    "                break  # 则结束\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "      adj = defaultdict(list)\n",
    "      for i,j in edges:\n",
    "        adj[i].append(j)\n",
    "        adj[j].append(i)\n",
    "      def bfs(start):\n",
    "        used = [False]*n\n",
    "        dist = [0]*n\n",
    "        queue = deque([[start, price[start]]])\n",
    "        used[start] = True\n",
    "        far = -1\n",
    "        max_l = 0\n",
    "        while queue:\n",
    "          cur, d = queue.popleft()\n",
    "          dist[cur] = d\n",
    "          if d>max_l:\n",
    "            max_l = d\n",
    "            far = cur\n",
    "          for i in adj[cur]:\n",
    "            if used[i]:\n",
    "              continue\n",
    "            used[i] = True\n",
    "            queue.append([i,d+price[i]])\n",
    "        return dist, far\n",
    "      _, s = bfs(0)\n",
    "      dist_to_s, t = bfs(s)\n",
    "      dist_to_t, _ = bfs(t)\n",
    "      ans = 0\n",
    "      for i in range(n):\n",
    "        ans = max(ans, max(dist_to_s[i], dist_to_t[i]) - price[i])\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        e = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            e[u].append(v)\n",
    "            e[v].append(u)\n",
    "        \n",
    "        f = [[0] * 3 for _ in range(n)]\n",
    "        \n",
    "        def dfs1(u: int, p: int):\n",
    "            f[u][0] = price[u]\n",
    "            for v in e[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                dfs1(v, u)\n",
    "                # 更新向下的最大价值和\n",
    "                if f[u][0] < f[v][0] + price[u]:\n",
    "                    f[u][1] = f[u][0]\n",
    "                    f[u][0] = f[v][0] + price[u]\n",
    "                elif f[u][1] < f[v][0] + price[u]:\n",
    "                    f[u][1] = f[v][0] + price[u]\n",
    "        \n",
    "        def dfs2(u: int, p: int):\n",
    "            for v in e[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                # 更新向上的最大价值和\n",
    "                if f[u][0] == f[v][0] + price[u]:\n",
    "                    # v 在 u 向下的最大价值和路径上\n",
    "                    f[v][2] = max(f[u][2], f[u][1]) + price[v]\n",
    "                else:\n",
    "                    f[v][2] = max(f[u][2], f[u][0]) + price[v]\n",
    "                dfs2(v, u)\n",
    "        \n",
    "        dfs1(0, -1)\n",
    "        dfs2(0, -1)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, f[i][0] - price[i], f[i][2] - price[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        # 建无向图\n",
    "        g = [set() for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        # 额外要记录的节点信息\n",
    "        s = price.copy()  # 当前最大带叶子的路径和\n",
    "        t = [0] * n  # 当前最大不带叶子的路径和\n",
    "        # 找出图中初始叶子节点，入队\n",
    "        q = deque(i for i, d in enumerate(g) if len(d) == 1)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            a = q.popleft()  # 叶子节点\n",
    "            b = g[a].pop()  # 取上级节点\n",
    "            g[b].remove(a)  # 并删除该边\n",
    "            # 记录b节点子树中经过b的最长路径\n",
    "            # 可能是当前最大不带叶子的路径和 + 当前带叶子的路径和\n",
    "            # 或者是当前最大带叶子的路径和 + 当前不带叶子的路径和\n",
    "            ans = max(ans, s[a] + t[b], t[a] + s[b])\n",
    "            # 记录b节点的最大带叶子的路径和和不带叶子的路径和\n",
    "            s[b] = max(s[b], s[a] + price[b])\n",
    "            t[b] = max(t[b], t[a] + price[b])\n",
    "            if len(g[b]) == 1:  # 当上级节点变为叶子节点\n",
    "                q.append(b)  # 则上级节点入队\n",
    "            elif not g[b]:  # 因刚删的边，已仅剩最后一个孤立节点\n",
    "                break  # 则结束\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # 返回带叶子的最大路径和，不带叶子的最大路径和\n",
    "        @cache\n",
    "        def dfs(x: int, fa: int) -> (int, int):\n",
    "            nonlocal ans\n",
    "            max_s1 = p = price[x]\n",
    "            max_s2 = 0\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                s1, s2 = dfs(y, x)\n",
    "                # 前面最大带叶子的路径和 + 当前不带叶子的路径和\n",
    "                # 前面最大不带叶子的路径和 + 当前带叶子的路径和\n",
    "                ans = max(ans, max_s1 + s2, max_s2 + s1)\n",
    "                max_s1 = max(max_s1, s1 + p)\n",
    "                max_s2 = max(max_s2, s2 + p)  # 这里加上 p 是因为 x 必然不是叶子\n",
    "            return max_s1, max_s2\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        agraph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        self.dfs(graph, 0, set([0]), agraph)\n",
    "        table = [0] * n\n",
    "        self.res = self.getMaxValStatic(agraph, price, 0, table)\n",
    "        # print(self.res, table)\n",
    "        upMax = [0] * n\n",
    "        self.getMaxValDynamic(agraph, price, 0, table, upMax)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, graph, node, visited, agraph):\n",
    "        for anode in graph[node]:\n",
    "            if anode not in visited:\n",
    "                agraph[node].append(anode)\n",
    "                visited.add(anode)\n",
    "                self.dfs(graph, anode, visited, agraph)\n",
    "    \n",
    "    def getMaxValStatic(self, agraph, price, node, table):\n",
    "        maxVal = 0\n",
    "        for anode in agraph[node]:\n",
    "            maxVal = max(maxVal, self.getMaxValStatic(agraph, price, anode, table) + price[anode])\n",
    "        table[node] = maxVal\n",
    "        return maxVal\n",
    "\n",
    "    def getMaxValDynamic(self, agraph, price, node, table, upMax):\n",
    "        vals = []\n",
    "        for anode in agraph[node]:\n",
    "            vals.append([table[anode] + price[anode], anode])\n",
    "        vals.sort(reverse = True)\n",
    "        for anode in agraph[node]:\n",
    "            bestVal = 0\n",
    "            if len(vals) > 0:\n",
    "                if vals[0][1] != anode: \n",
    "                    bestVal = vals[0][0]\n",
    "                else:\n",
    "                    if len(vals) > 1:\n",
    "                        bestVal = vals[1][0]             \n",
    "            bestUpVal = price[node] + max(upMax[node], bestVal)\n",
    "            upMax[anode] = bestUpVal\n",
    "            self.res = max(self.res, upMax[anode], table[anode])\n",
    "            # print(max(upMax[anode], table[anode]), anode, upMax[anode], table[anode], upMax[node], bestVal, vals)\n",
    "            self.getMaxValDynamic(agraph, price, anode, table, upMax)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        child = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            child[a].add(b)\n",
    "            child[b].add(a)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(node, pre):\n",
    "            nonlocal ans\n",
    "            a, b = price[node], 0\n",
    "\n",
    "            for ch in child[node]:\n",
    "                if ch != pre:\n",
    "                    s1, s2 = dfs(ch, node)\n",
    "\n",
    "                    ans = max(ans, a + s2, b + s1)\n",
    "                    a = max(a, s1 + price[node])\n",
    "                    b = max(b, s2 + price[node])\n",
    "\n",
    "            return a, b\n",
    "\n",
    "        dfs(0, -1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        d1, d2, s1, s2 = [0] * n, [0] * n, [0] * n, [0] * n\n",
    "        up = [0] * n\n",
    "        res = 0\n",
    "        dfd = defaultdict(list)\n",
    "\n",
    "        for a, b in edges:\n",
    "            dfd[a].append(b)\n",
    "            dfd[b].append(a)\n",
    "        \n",
    "        def dfs_d(u, p):\n",
    "\n",
    "            for ne in dfd[u]:\n",
    "                if ne != p:\n",
    "                    dfs_d(ne, u)\n",
    "                    if d1[ne] >= d1[u]:\n",
    "                        d2[u], s2[u] = d1[u], s1[u]\n",
    "                        d1[u], s1[u] = d1[ne] , ne\n",
    "                    elif d1[ne] > d2[u]:\n",
    "                        d2[u], s2[u] = d1[ne], ne\n",
    "            d1[u] += price[u]\n",
    "            d2[u] += price[u]\n",
    "        \n",
    "        def dfs_u(u, p):\n",
    "            nonlocal res\n",
    "            if p == -1: up[u] = price[u]\n",
    "            for ne in dfd[u]:\n",
    "                if ne != p:\n",
    "                    if s1[u] == ne: up[ne] = max(d2[u], up[u]) + price[ne]\n",
    "                    else: up[ne] = max(d1[u], up[u]) + price[ne]\n",
    "                    dfs_u(ne, u)\n",
    "            res = max(res, max(d1[u], up[u]) - price[u])\n",
    "\n",
    "        dfs_d(0, -1)\n",
    "        dfs_u(0, -1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        top2_sublen = [[0,0] for _ in range(n)]\n",
    "        ans = [0]*n\n",
    "        d = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            d[a].append(b)\n",
    "            d[b].append(a)\n",
    "        # print(d)\n",
    "\n",
    "        def dfs(a,fa):\n",
    "            for b in d[a]:\n",
    "                if b!=fa:\n",
    "                    cur = dfs(b,a)+price[b]\n",
    "                    # print(b, a, cur)\n",
    "                    if cur>top2_sublen[a][0]:\n",
    "                        top2_sublen[a][1] = top2_sublen[a][0]\n",
    "                        top2_sublen[a][0] = cur\n",
    "                    elif cur>top2_sublen[a][1]:\n",
    "                        top2_sublen[a][1] = cur\n",
    "                    # print(top2_sublen)\n",
    "            return top2_sublen[a][0]\n",
    "        \n",
    "        ans[0] = dfs(0,-1)\n",
    "        # print(top2_sublen)\n",
    "\n",
    "        def reroot(a, fa, behind):\n",
    "            # print(a,fa,behind)\n",
    "            cur = price[a]\n",
    "            ans[a] = max(behind, top2_sublen[a][0])\n",
    "            for b in d[a]:\n",
    "                if b!=fa:\n",
    "                    if top2_sublen[b][0]+price[b]==top2_sublen[a][0]:\n",
    "                        behind_b = max(behind, top2_sublen[a][1])\n",
    "                        # print(b, a, behind_b,'aaa')\n",
    "                    else:\n",
    "                        behind_b = max(behind, top2_sublen[a][0])\n",
    "                        # print(b, a, behind_b,'bbb')\n",
    "                    reroot(b,a,behind_b+cur)\n",
    "            # print(ans)\n",
    "            return \n",
    "\n",
    "        reroot(0,-1,0)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n",
    "        e = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            e[u].append(v)\n",
    "            e[v].append(u)\n",
    "        \n",
    "        f = [[0] * 3 for _ in range(n)]\n",
    "        \n",
    "        def dfs1(u: int, p: int):\n",
    "            f[u][0] = price[u]\n",
    "            for v in e[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                dfs1(v, u)\n",
    "                # 更新向下的最大价值和\n",
    "                if f[u][0] < f[v][0] + price[u]:\n",
    "                    f[u][1] = f[u][0]\n",
    "                    f[u][0] = f[v][0] + price[u]\n",
    "                elif f[u][1] < f[v][0] + price[u]:\n",
    "                    f[u][1] = f[v][0] + price[u]\n",
    "        \n",
    "        def dfs2(u: int, p: int):\n",
    "            for v in e[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                # 更新向上的最大价值和\n",
    "                if f[u][0] == f[v][0] + price[u]:\n",
    "                    # v 在 u 向下的最大价值和路径上\n",
    "                    f[v][2] = max(f[u][2], f[u][1]) + price[v]\n",
    "                else:\n",
    "                    f[v][2] = max(f[u][2], f[u][0]) + price[v]\n",
    "                dfs2(v, u)\n",
    "        \n",
    "        dfs1(0, -1)\n",
    "        dfs2(0, -1)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, f[i][0] - price[i], f[i][2] - price[i])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
